/*
 * DSBDirect
 * Copyright (C) 2020 Fynn Godau
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * This software is not affiliated with heinekingmedia GmbH, the
 * developer of the DSB platform.
 */

package godau.fynn.dsbdirect.table.entry.expression;

import android.util.Log;
import androidx.annotation.VisibleForTesting;
import godau.fynn.dsbdirect.table.TableColumn;
import godau.fynn.dsbdirect.table.entry.Entry;

import java.util.ArrayList;

abstract class Expression {

    public abstract String format(Entry e);

    @VisibleForTesting(otherwise = VisibleForTesting.PROTECTED)
    public static ArrayList<Expression> parse(String s) {

        ArrayList<Expression> expressions = new ArrayList<>();

        char[] expressionChars = (s + ',').toCharArray();

        int bracketLevel = 0;
        int bracketBegin = -1;
        int elementaryExpressionBegin = 0;
        for (int i = 0; i < expressionChars.length; i++) {

            switch (expressionChars[i]) {
                case '(':
                    if (bracketLevel > 0) {
                        expressionChars[i] = ' ';
                    } else {
                        bracketBegin = i;
                    }
                    bracketLevel++;
                    break;

                case ')':
                    bracketLevel--;
                    if (bracketLevel > 0) {
                        expressionChars[i] = ' ';
                    }
                    if (bracketLevel == 0) {
                        expressions.add(new OrExpression(new String(expressionChars).substring(bracketBegin+1, i)));
                        elementaryExpressionBegin = i+1;
                    }
                    break;

                case ',':
                    if (bracketLevel == 0) {
                        String e = new String(expressionChars).substring(elementaryExpressionBegin, i);
                        if (e.length() > (e = e.replaceAll("~", "")).length()) { // True if ~ has been removed
                            expressions.add(new NotExpression(e));
                        } else {
                            expressions.add(new ElementaryExpression(e));
                        }
                        elementaryExpressionBegin = i + 1;
                    }
                    break;
            }

            if (bracketLevel < 0) {
                Log.wtf("EXPRESSION", "parse() received invalid input; validate input first!");
                throw new InvalidExpressionException();
            }
        }

        return expressions;
    }

    /**
     * Validates input by bringing it into a form that can be validated by {@link #CYK(String)}.
     *
     * @see #CYK(String)
     */
    public static boolean validate(String s) {

        // Replace enum constants with s
        TableColumn[] values = TableColumn.values();
        for (int i = values.length - 1; i >= 0; i--) { // Inverted because OLD_ enums are at the bottom
            TableColumn tc = values[i];
            s = s.replaceAll(tc.toString(), "s");
        }
        s = s.replaceAll(" ", "");
        System.out.println(s);

        return CYK(s);
    }

    /**
     * Validates the string parameter against the following context-free grammar
     * in a form similar to the Chomsky norm form:
     *
     * <pre><code>
     * G' = (Σ, {A, B, S}, S, R')
     * Σ = {s, ',', (, ), ~}
     * R' = {
     * 	S → SA
     * 	A → ,S
     * 	S → (B
     * 	B → S)
     * 	S → ~S
     * 	S → s
     * } with s ∈ Σ
     * </code></pre>
     *
     * It is equivalent to the following grammar:
     *
     * <pre><code>
     * G = (Σ, {S}, S, R)
     * R = {
     * 	S → S,S
     * 	S → (S)
     * 	S → ~S
     * 	S → s
     * } with s ∈ Σ
     * </code></pre>
     *
     * For this, it utilises a slightly modified form of the CYK algorithm.
     *
     * @return True if s can be generated from this grammar
     */
    private static boolean CYK(String s) {

        int n = s.length();
        if (n == 0) return true;

        boolean[][] A, B, S;
        A = new boolean[n][n];
        B = new boolean[n][n];
        S = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 's') S[i][i] = true;
        }

        for (int k = 1; k < n; k++) {
            for (int i = 0; i < n-k; i++) {
                for (int j = i; j < i+k; j++) {
                    if (S[i][j] && A[j+1][i+k]) S[i][i+k] = true;
                    if (s.charAt(i) == ',' && i == j && S[j+1][i+k]) A[i][i+k] = true;
                    if (s.charAt(i) == '(' && i == j && B[j+1][i+k]) S[i][i+k] = true;
                    if (S[i][j] && s.charAt(j+1) == ')' && j+1 == i+k) B[i][i+k] = true;
                    if (s.charAt(i) == '~' && i == j && S[j+1][i+k]) S[i][i+k] = true;
                }
            }
        }

        return S[0][n-1];
    }

    public static class InvalidExpressionException extends IllegalArgumentException {}
}
